package com.cn.test.record;

/**
 * description: 链表相关操作
 *
 * @author twj
 * @date 2021/7/23 10:54 .
 */
public class LinkedList {
    private ListNode head;
    private int size;

    public LinkedList() {
        this.head = null;
        this.size = 0;
    }

    public void addAtHead(int val) {
        ListNode n = new ListNode(val);
        n.next = this.head;
        this.head = n;
        this.size++;
    }

    public void addAtIndex(int index, int val) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("index is error");
        }
        if (index == 0) {
            addAtHead(val);
            return;
        }
        ListNode pre = this.head;
//        要插入结点的前一个节点pre
        for (int i = 0; i < index - 1; i++) {
            pre = pre.next;
        }
        ListNode node = new ListNode(val);
//        要插入的节点的下一个节点指向pre节点的下一个节点
        node.next = pre.next;
//        前一个节点的下一个节点指向要插入的节点
        pre.next = node;
        this.size++;
    }

    public void addAtTail(int val) {
        if (size < 1) {
            addAtHead(val);
        } else {
            ListNode cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = new ListNode(val);
            size++;
        }

    }

    public void remove(int val) {
        if (head == null) {
            System.out.println("无元素可删除");
            return;
        }
//        删除的节点与头节点元素相同
        while (head != null && head.val == val) {
            head = head.next;
            size--;
        }
//        头节点的下一个节点
        ListNode cur = this.head;
        while (cur != null && cur.next != null) {
            if (cur.val == val) {
                this.size--;
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
    }

    public int removeFirst() {
        if (this.head == null) {
            System.out.println("无元素可删除");
            return -1;
        }
        ListNode del = this.head;
        this.head = this.head.next;
        del.next = null;
        this.size--;
        return del.val;
    }

    public int removeLast() {
        if (this.head == null) {
            System.out.println("无元素可删除");
            return Integer.MAX_VALUE;
        }
        if (size == 1) {
            return removeFirst();
        }
        ListNode cur = this.head;
        ListNode pre = this.head;
        while (cur.next != null) {
            pre = cur;
            cur = cur.next;
        }
        pre.next = cur.next;
        this.size--;
        return cur.val;
    }

    public void deleteAtIndex(int index) {

        if (index == 0) {
            ListNode del = this.head;
            this.head = this.head.next;
            del.next = null;
            size--;

        } else if (index < size) {
            ListNode curr = head, pre = head;
            int count = 0;
            while (curr.next != null && count < index) {
                pre = curr;
                curr = curr.next;
                count++;
            }
            pre.next = curr.next;
            this.size--;
        }
    }

    public boolean contains(int val) {
        ListNode cur = this.head;
        while (cur.next != null) {
            if (cur.val == val) {
                return true;
            } else {
                cur = cur.next;
            }
        }
        return false;
    }

    @Override
    public String toString() {

        StringBuffer sb = new StringBuffer();
        ListNode cur = this.head;
        while (cur != null) {
            sb.append(cur.val + " -> ");
            cur = cur.next;
        }
        sb.append("NULL");
        return sb.toString();
    }

    public int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        if (size<1) return -1;
        ListNode curr = head;
        for (int i = 0; i < index; i++) {
            curr = curr.next;
        }
        return curr.val;
    }

    public static void main(String[] args) {
        LinkedList node = new LinkedList();
        node.addAtHead(1);

        node.addAtTail(3);
        node.addAtIndex(1,2);
        node.get(1);
        node.deleteAtIndex(1);
        node.get(1);
        node.get(3);
        node.deleteAtIndex(3);
        node.deleteAtIndex(0);
        node.get(0);
        System.out.println(node);
        node.deleteAtIndex(0);
        System.out.println(node);
        System.out.println("--size"+node.size);
        node.get(0);


        System.out.println(node);



    }
}
